public class Test4 {
    public ListNode sortList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }

        //找到链表中点
        ListNode mid = findMid(head);
        ListNode right = mid.next;
        mid.next = null;

        //递归地对两个子链表进行排序
        ListNode sortedLeft = sortList(head);
        ListNode sortedRight = sortList(right);

        //合并两个有序子链表
        return merge(sortedLeft,sortedRight);
    }

    private ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    private ListNode merge(ListNode l1,ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                curr.next = l1;
                l1 = l1.next;
            }else{
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if(l1 != null){
            curr.next = l1;
        }
        if(l2 != null){
            curr.next = l2;
        }
        return dummyHead.next;
    }
}
